package LeetCode;

import java.util.Arrays;

public class Code53 {
    // 寻找一个数组的最长子序列和
    public int maxSubArray(int[] nums) { //1 <= nums.length <= 3 * 104  //使用穷举法
        // 第一件事，排除不合理数组
        if (nums.length == 1)
            return nums[0];
        int result = nums[0];
        for (int i = 0; i < nums.length; i++) {
            int ans = nums[i];
            if (ans > result)
                result = ans;
            for (int j = i+1; j < nums.length; j++) {
                ans += nums[j]; // 记录每次的值，每次的起点不同，我们记录这个起点下的所有值
                if (ans > result)
                    result = ans;
            }
        }
        return result;
        //1 <= nums.length <= 3 * 104  //使用穷举法
    }

    public int maxSubArray2(int[] nums) { //1 <= nums.length <= 3 * 104  //使用动态规划
        // 第一件事，排除不合理数组
        if (nums.length == 1)
            return nums[0];
        int[] answer = new int[nums.length]; // answer代表结果集 // 这里很妙！！
        answer[0] = nums[0];
        for (int n = 1; n < answer.length; n++) {
            answer[n] = Math.max(nums[n],nums[n] + answer[n-1]);
        }
        Arrays.sort(answer);
        return answer[answer.length-1];
    }

    public int maxSubArray3(int[] nums) { //1 <= nums.length <= 3 * 104  //使用动态规划 // 代码优化
        // 第一件事，排除不合理数组
        if (nums.length == 1)
            return nums[0];
        int answer = nums[0],pre = 0; // answer代表结果集 // 这里很妙！！ 每次只需要前一个值。而我们需要的是其中最大的
        for (int n = 0; n < nums.length; n++) {
            pre = Math.max(nums[n], pre + nums[n]);
            answer = Math.max(pre,answer);
        }
        return answer;
    }

    public int maxSubArray4(int[] nums) { //1 <= nums.length <= 3 * 104  //分治法
        return 0;
    }


    public static void main(String[] args) {
        Code53 code53 = new Code53();
//        System.out.println("code53.maxSubArray(new int[]{-2,1}) = " + code53.maxSubArray2(new int[]{-2, 1}));

        System.out.println("code53.maxSubArray(new int[]{-2,1,-3,4,-1,2,1,-5,4}) = " + code53.maxSubArray2(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
        System.out.println("code53.maxSubArray(new int[]{0}) = " + code53.maxSubArray2(new int[]{0}));
        System.out.println("code53.maxSubArray(new int[]{-1000}) = " + code53.maxSubArray2(new int[]{-1000}));
    }
}
